#include <vector> 
#include <cmath>
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <limits>
#include <chrono>

using namespace std;

class Matriz
{  
public:
    vector<vector<int> > w1,w2;
    int n,m,u,v,K;
    Matriz();
};


Matriz::Matriz()
{
  int x,y,peso1,peso2;
  cin >> n; // n vertic
  if(n == 0)
    exit(0);
  cin >> m; // m aristas
  cin >> u; // vertice inicial
  u = u-1;
  cin >> v; // vertice final
  v = v-1;
  cin >> K; // cota a respetar de w1
  w1.resize(n);
  w2.resize(n);
  for(int i = 0; i < n; i++)
  {
    w1[i].resize(n);
    w2[i].resize(n);
  }
  
  
  for(int i = 0; i < n; i++) 
  {
    for(int j = 0; j < n; j++) 
    {
      w1[i][j] = numeric_limits<int>::min();
      w2[i][j] = numeric_limits<int>::min();
    }
  }
  
  for(int i = 0; i < m; i++) 
  {
    cin >> x;
    cin >> y;
    cin >> peso1;
    cin >> peso2;
    w1[x-1][y-1] = peso1;
    w2[x-1][y-1] = peso2;
    w1[y-1][x-1] = peso1;
    w2[y-1][x-1] = peso2;
  }
}

bool seFormaCiclo(const vector<int>* sol)
{
   int ultimoNodo = sol->back();
   for(int i=0; i < sol->size() -1; i++)
     if(ultimoNodo == (*sol)[i])
       return true;
   return false;
}

int sumarW(const vector<int>* sol, const vector<vector<int> >* w)
{
   int x,y;
   int suma = 0;
   for(int i=1; i < sol->size(); i++)
   {
    x = (*sol)[i-1];
    y = (*sol)[i];
    suma = (*w)[x][y] + suma;
   }
   return suma;
}

int backtrack(Matriz *matriz, int *mejorSol,vector<int>* solFinal,vector<int>* solParcial)
{
  /*************************
  Backtrack(matriz, x, y) (estoy en un nodo (x,y))
    w1 mayor que K?
      descarto solucion, no cumple lo pedido.
    w2 mayor que la mejor solucion encontrada?
      podo.
    LLuegé al final?
      guardo sol y sigo buscando.
    se formó un ciclo?
      descarto la solucion, debe haber una mejor.
   pruevo a saltar a todos los nodos adyacentes 
  ****************************/
  int sumaW1 = sumarW(solParcial,&matriz->w1);
  int sumaW2 = sumarW(solParcial,&matriz->w2);
  
  
  if( sumaW1 > matriz->K )
    return 1;
  if( sumaW2 > (*mejorSol) )
    return 1;
  //Chequeo si llegue al final
  if(solParcial->back() == matriz->v)
  {
    //si si, la remplazo por la que tenia hasta ahora.
    (*mejorSol) = sumaW2;
    solFinal->resize(solParcial->size());
    copy(solParcial->begin(),solParcial->end(),solFinal->begin());
    return 0;
  }
  //Chequeo si se formo un ciclo, en caso afirmativo, debe existir una mejor sol, corto
  if(seFormaCiclo(solParcial) == true)
    return 1; //Tirar Sol
  
  // Hago backtrack
  for(int i = 0; i< matriz->n; i++)
  {
    if(numeric_limits<int>::min() != matriz->w1[solParcial->back()][i])
    {
      solParcial->push_back(i);
      backtrack(matriz,mejorSol,solFinal,solParcial);
      solParcial->pop_back();
    }
  }
}

int main()
{
  while(true)
  {
    Matriz matriz = Matriz();
    int mejorSol = numeric_limits<int>::max();
    vector<int> solParcial,solFinal;
    
    solParcial.push_back(matriz.u);
    // MEDICION TIEMPO
    auto start = chrono::high_resolution_clock::now();
    // FIN MED
    backtrack(&matriz, &mejorSol,&solFinal, &solParcial);
    // MED TIEMPO
    auto finish = chrono::high_resolution_clock::now();
    cout << chrono::duration_cast<chrono::microseconds>(finish - start).count() << endl;
    // FIN MED TIEMPO
    if(solFinal.size() != 0)
    {
      cout << sumarW(&solFinal,&matriz.w1) << " "; // Imprimo tamanio w1
      cout << sumarW(&solFinal,&matriz.w2) << " ";// Imprimo tamanio w2
      cout << solFinal.size() << " "; // Imprimo tamanio del camino
      
      for(int i = 0; i < solFinal.size(); i++) // Imprimo camino
	cout << solFinal[i]+1 << " ";
      cout << endl;
    }else
      cout << "no" << endl;
  }
  return 0;
}